10.8 KB · ⇊ 3 parts · ⤓ Micron 10.8 KB · ⤓ HTML 33.4 KB

top

Nella mwawteoria della complessità computazionale la mwbaclasse di complessità mwbqEXPTIME (a volte chiamata mwbgEXP, da mwbwExponential Time, "tempo esponenziale"), è l'mwcainsieme di tutti i mwcqproblemi decisionali risolvibili da una mwcgmacchina deterministica di Turing nel tempo mwcwO(2mwdamwdqp(mwdgn)), dove mwdwp(mwean) è una funzione polinomiale di mweqn.

In termini di DTIME,

mwfg EXPTIME = ⋃ ⋃ k ∈ ∈ N DTIME ( 2 n k ) . {\displaystyle {\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{n^{k}}\right).}

Sappiamo che

mwggP mwgw ⊆ ⊆ {\displaystyle \subseteq } mwhaNP mwhq ⊆ ⊆ {\displaystyle \subseteq } mwhgPSPACE mwhw ⊆ ⊆ {\displaystyle \subseteq } EXPTIME mwia ⊆ ⊆ {\displaystyle \subseteq } mwiqNEXPTIME mwig ⊆ ⊆ {\displaystyle \subseteq } mwiwEXPSPACE

e inoltre, dal teorema della gerarchia temporale e dal teorema della gerarchia spaziale, che

P mwkq ⊊ ⊊ {\displaystyle \subsetneq } EXPTIMEmwkg emwkw NP mwla ⊊ ⊊ {\displaystyle \subsetneq } NEXPTIMEmwlq emwlg PSPACE mwlw ⊊ ⊊ {\displaystyle \subsetneq } EXPSPACE

così almeno una delle prime tre inclusioni e almeno una delle ultime tre inclusioni deve essere corretta, ma non si sa quali sono, anche se la maggior parte degli esperti credono che tutte le inclusioni siano corrette. Si sa anche che se mwmqP = NP, allora mwmgEXPTIME = NEXPTIME, la classe dei problemi risolvibili nel tempo esponenziale da una mwmwmacchina di Turing non deterministica.cite-ref-1[1] Più precisamente, mwoaEXPTIME ≠ mwoqNEXPTIME mwogse e solo se esistono linguaggi sparsi in mwpaNP che non sono in mwpqP.cite-ref-2[2]

EXPTIME può anche essere riformulato come la classe di spazio APSPACE, i problemi che possono essere risolti da una macchina di Turing alternante nello spazio polinomiale. Questo è un modo di vedere che PSPACE mwrq ⊆ ⊆ {\displaystyle \subseteq } EXPTIME, poiché una macchina di Turing alternante è potente almeno quanto una macchina di Turing deterministica.cite-ref-3[3]

EXPTIME è una classe in una mwswgerarchia esponenziale di classi di complessità con limiti temporali sempre più alti. La classe mwta2-EXPTIME è definita similmente a EXPTIME, ma con un limite temporale mwtqdoppiamente esponenziale mwtg 2 2 n {\displaystyle 2^{2^{n}}} . Questo può essere generalizzato a limiti temporali sempre più alti.

• EXPTIME-completo

• Note

Un problema decisionale è mwuqEXPTIME-completo se è in EXPTIME, e ogni problema in EXPTIME ha una riduzione di tempo polinomiale ad esso. In altre parole, c'è un mwuwalgoritmo di tempo polinomiale che trasforma richieste dell'uno in richieste dell'altro con la stessa risposta. I Problemi che sono EXPTIME-completi potrebbero essere pensati come i problemi più difficili in EXPTIME. Si noti che sebbene non sappiamo se NP è o no un sottoinsieme di P, sappiamo però che i problemi EXPTIME-completi non sono in P; è stato provato, dal teorema della gerarchia temporale, che questi problemi non possono essere risolti nel mwvqtempo polinomiale.

Nella mwvwteoria della computabilità, uno dei problemi indecidibili basilari è quello di decidere se una mwwamacchina deterministica di Turing (MDT) si arresta. Uno dei più fondamentali problemi EXPTIME-completi p una versione più semplice di questo, che chiede se una MDT si arresta al massimo in mwwqk passi. Se è in EXPTIME perché una simulazione banale richiede il tempo O(mwwgk), e l'ingresso mwwwk è codificato usando O(log mwxak) bit.cite-ref-4[4] È EXPTIME-completo perché, parlando all'ingrosso, possiamo usarlo per verificare se una macchina che risolve un problema EXPTIME accetta un numero esponenziale di passi; non ne userà di più. Lo stesso problema con il numero di passi scritto in unario è P-completo.

Altri esempi di problemi EXPTIME-completi includono il problema di valutare una posizione negli mwywscacchi,cite-ref-fraenkel1981-5-0[5] nella mwaadama,cite-ref-robson1984-6-0[6] o nel mwbqgo (con le regole giapponesi del ko)cite-ref-7[7] di tipo generalizzato. Questi giochi hanno una probabilità di essere EXPTIME-completi perché i giochi possono durare per un numero di mosse che è esponenziale alla dimensione della scacchiera. Nell'esempio del go, la regola giapponese del ko è sufficientemente intrattabile da implicare la completezza EXPTIME, ma non si sa se le regole più trattabili per il gioco americane o cinesi siano EXPTIME-complete.

Per contrasto, i giochi generalizzati che possono durare per un numero di mosse che è polinomiale alla dimensione della scacchiera sono spesso mwdaPSPACE-completi. Lo stesso è vero per i giochi esponenzialmente lunghi in cui la non ripetizione è automatica.

Un altro insieme di importanti problemi EXPTIME-completi si riferisce ai circuiti succinti. I circuiti succinti sono macchine semplici usate per descrivere alcuni grafi in esponenzialmente meno spazio. Essi accettano due numeri di vertice come ingresso e uscita se c'è un margine tra di essi. Per molti problemi di grafi P-completi naturali, dove il mweagrafo è espresso in una rappresentazione naturale come una mweqmatrice delle adiacenze, risolvere lo stesso problema su una rappresentazione di un circuito succinto è EXPTIME-completo, perché l'ingresso è esponenzialmente più piccolo; ma questo richiede prove non banali, dal momento che i circuiti succinti possono soltanto descrivere una sottoclasse di grafi.cite-ref-8[8]

cite-note-11. ↑ mwhamwhqChristos Papadimitriou, mwhgmwhwComputational Complexity, Addison-Wesley, 1994, mwiaISBNmwiq 0-201-53082-1. sezione 20.1, p. 491.

cite-note-22. ↑ Juris Hartmanis, Neil Immerman, Vivian Sewelson. "Sparse Sets in NP-P: EXPTIME versus NEXPTIME". mwjgInformation and Control, volume 65, numeri 2/3, pp. 158–181. 1985. mwjwSu ACM Digital Library

cite-note-33. ↑ Papadimitriou (1994), sezione 20.1, corollario 3, p. 495.

cite-note-44. ↑ mwlgChris Umans, mwlwmwmaCS 21: Lecture 16 notes (mwmqmwmgPDF), su mwmwcs.caltech.edu mwna(archiviato dall'mwnqurl originale l'8 giugno 2011). Diapositiva 21.

cite-note-fraenkel1981-55. ↑ mwoqAviezri Fraenkel e D. Lichtenstein, mwowComputing a perfect strategy for nmwpa×n chess requires time exponential in n, in mwpqJ. Comb. Th. A, n.mwpg 31, 1981, pp.mwpw 199-214.

cite-note-robson1984-66. ↑ mwqwJ. M. Robson, mwramwrqN by N checkers is Exptime complete, in mwrgSIAM Journal on Computing,, vol.mwrw 13, n.mwsa 2, 1984, pp.mwsq 252-267, mwsgDOI:mwsw10.1137/0213018.

cite-note-77. ↑ mwtwJ. M. Robson, mwuaThe complexity of Go, in mwuqInformation Processing; Proceedings of IFIP Congress, 1983, pp.mwug 413-417.

cite-note-88. ↑ Papadimitriou (1994), sezione 20.1, p. 492.